# Divide and Conquer

• 2026년 7월 27일 알고리즘
  카라츠바 알고리즘 — n자리 곱셈은 n²보다 빠를 수 있다

  n자리 두 수를 곱하는 데 정의대로면 Θ(n²)이 든다. 반으로 잘라 재귀해도 곱셈이 4번이라 여전히 n²이다. 카라츠바는 (x₁+x₂)(y₁+y₂) 하나로 곱을 3번으로 줄여 Θ(n^1.585)를 얻는다. Strassen의 8→7과 같은 구조를, 한 단계 더 단순한 무대에서 본다.

• 2026년 7월 23일 알고리즘
  행렬 곱셈 — 나누기만으로는 못 이긴다, Strassen이 곱을 줄이는 법

  N×N 행렬 곱은 정의대로면 O(N³)이다. 2×2 블록으로 나눠 재귀해도 곱셈이 8번이라 여전히 N³이다. Strassen은 곱셈을 7번으로 줄여 O(N^2.807)을 얻는다. 왜 지수가 바뀌는지, 7개의 곱이 답을 재구성하는지 검증한다.

• 2026년 7월 13일 알고리즘
  볼록 껍질 ④ — 분할 정복과 공통 접선

  점들을 절반으로 갈라 각각의 껍질을 재귀로 구한 뒤 공통 접선(common tangent)으로 잇는 분할 정복을 다룬다. 접선을 O(N)에 찾는 선형 워킹을 증명까지 따라가고, 이진 탐색을 겹쳐 O(log²N)으로 줄이는 아이디어와 그 아이디어가 아직 채우지 못한 부분을 밝힌다.

• 2026년 7월 1일 알고리즘
  가장 가까운 점 쌍 ② — 정렬을 유지해 O(n log n)으로

  1편 O(n log²n)의 여분 log n은 combine마다 y정렬을 다시 하는 데서 나온다. 재귀가 y로 정렬된 결과를 반환하게 만들어 combine을 O(n) merge로 바꾸고, 분할은 x·순서는 y로 유지해 전체를 O(n log n)으로 끌어내린다.

• 2026년 6월 30일 알고리즘
  가장 가까운 점 쌍 ① — 분할 정복과 O(n log²n)

  2차원 평면에서 가장 가까운 두 점을 찾는 문제. 모든 쌍을 보면 O(n²)이지만, 분할 정복으로 더 빠르게 풀 수 있다. x좌표로 좌우를 나눠 각 영역의 최소 거리 D를 구한 뒤, 경계의 폭 D 밴드만 합치는 과정을 보고 O(n log²n)임을 유도한다.

• 2026년 6월 27일 알고리즘
  quick sort — 최악 O(n²)인데 평균은 왜 O(n log n)인가

  quick sort는 pivot으로 배열을 가르는 분할 정복이다. 두 포인터 분할 과정을 보고 최선 O(n log n)과 최악 O(n²)이 갈리는 지점을 짚는다. 핵심은 평균 분석이다. 기댓값 점화식 E(n)을 세워 평균이 Θ(n log n)임을 유도한다.

• 2026년 6월 25일 알고리즘
  분할 정복 — 나누어 풀고, 정렬의 한계를 증명하다

  분할 정복은 문제를 나눠 풀고 합치는 전략이다. merge sort의 점화식을 대입법으로 풀어 O(n log n)을 유도하고, 메모리 약점과 대안 heap sort를 본다. 비교 기반 정렬이 Ω(n log n)보다 빠를 수 없음을 결정 트리로 증명한다.

• 2026년 4월 5일 알고리즘
  재귀 — 문제를 자기 자신으로 푼다

  재귀(Recursion)의 구조와 올바른 설계 원칙을 이해하고, 수학적 귀납법으로 재귀 알고리즘의 올바름을 증명한다. 팩토리얼·피보나치·하노이의 탑을 통해 재귀적 사고를 익히고, 재귀 트리와 마스터 정리로 복잡도를 분석한다.